package leetcode_201_220;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class minSubArrayLen_209 {
    /**
     * 前缀和写法
     * 要求找的是大于等于target
     * 这样用前缀和就没必要了
     */
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, Min_len = Integer.MAX_VALUE;
        //键为前缀和，值为最近出现的下标（没有要求找到所有）
        HashMap<Integer, Integer> map = new HashMap<>();
        //实时计算前缀和
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            map.put(sum, i);
            if (map.containsKey(sum - target))  //存在前缀和s+target=sum
                Min_len = Math.min(Min_len, i - map.get(sum - target));
        }
        return Min_len == Integer.MAX_VALUE ? 0 : Min_len;
    }

    /**
     * 滑动窗口
     */
    public int minSubArrayLen2(int target, int[] nums) {
        int sum = 0, l = 0, Min_len = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(sum>=target) {
                //当前窗口数值足够时，滑动左边界
                while (sum >= target)
                    sum -= nums[l++];
                Min_len = Math.min(Min_len, i - l + 2);  //因为满足条件的 l 向右了一位，窗口大小需要加1
            }
        }
        return Min_len == Integer.MAX_VALUE ? 0 : Min_len;
    }
}
